1. Field of the Invention
The invention relates generally to hashing systems and, in particular, to hashing systems that manipulate longer bit sequences to produce shorter hash values.
2. Background Information
Hashing functions are typically employed when it is desired to represent a bit sequence using different bits and, in particular, a smaller number of bits. The representation is referred to as a “hash value,” or simply as a “hash.” The original bit sequence is manipulated in accordance with a hash function, which is selected such that there is little likelihood that different “legitimate” bit sequences will, after manipulation, result in the same hash value, i.e., that the hash values will “collide.”
Known hashing systems employ shifting and arithmetic subtraction and/or multiplication operations to manipulate the bit sequences. The circuits to perform the arithmetic subtraction and multiplication operations are, however, relatively complex to implement, particularly when large numbers of bits must be manipulated.
There is a need for a reliable hashing of multiple bit identifiers of disk drives used in small-computer-systems-interface (SAS) environments (See International Committee for Information Technology Standards T10 Technical Committee, “Serial Attached SCSI” Rev. 03, Nov. 21, 2002.), to produce smaller sequences of bits that can be used as device identifiers in standard disk interface environments. More specifically, in an SAS environment the disk drives are identified by 64-bit world-wide-names (“WWNs”), which are also known as world-wide-unique identifiers (“WWUIs”). Over a conventional disk drive interface, however, the drive identifiers may be a maximum size of 24 bits. In order to communicate the 64 bit WWN through a conventional disk drive interface, the 64 bit WWN must thus be represented by a value of 24 or less bits, that is, the WWN must be reliably hashed to a smaller bit sequence. The system described below produces the hash values, without requiring the complex circuits of conventional hashing systems.